2667. Змейка

Напишите программу, которая выводит элемент из строки x и столбца y матрицы размера n × m, которая заполнена змейкой:

Вход. Даны натуральные числа n, m, x, y (1 ≤ x ≤ n ≤ 50, 1 ≤ y ≤ m ≤ 50). Здесь n – количество строк матрицы, m – количество столбцов матрицы, x и y – номера строки и столбца искомого элемента.

Выход. Вывести элемент из строки x и столбца y.

Пример входа	Пример выхода
5 2 3 1	4

РЕШЕНИЕ

двумерный массив

Анализ алгоритма

Будем заполнять двумерный целочисленный массив mas как сказано в условии задачи. Переменная cnt хранит значение, присваиваемое ячейкам массива. С каждым продвижением в следующую клетку ее значение будем увеличивать на 1.

Нам следует заполнить n строк, каждую из которых следует заполнять либо слева направо, либо справа налево. Объявим переменную dir, которая содержит 1 если движение по строке идет направо, и -1 если налево. Дойдя до конца строки (то ли левого то ли правого), нам следует перейти на следующую строку, при этом оставшись в текущей колонке. Меняем значение dir на противоположное и движемся далее в противоположную сторону.

Заполнив змейкой массив, остается вывести значение mas[x][y].

Реализация алгоритма

Объявим рабочий массив.

#define MAX 110

int mas[MAX][MAX];

Читаем входные данные.

scanf("%d %d %d %d",&n,&m,&x,&y);

Инициализируем движение змейкой. Движение начинается с первой колонки (j = 1) слева направо (dir = 1), значение cnt = 0 присваиваем первой ячейке массива.

dir = 1; j = 1; cnt = 0;

Переменная i содержит номер строки, j – номер столбца.

for(i = 1; i <= n; i++)

{

Двигаемся по i-ой строке пока не зайдем за ее границу – либо в 0 колонку, либо в (m+1)-ую. Номер колонки j после каждого шага изменяем на dir.

for(; (j >= 1) && (j <= m); j += dir)

mas[i][j] = cnt++;

Меняем направление движения на противоположное.

dir = -dir;

Возвращаемся в границы массива. Если мы находимся в 0-ой колонке, то вернемся в 1-ую. Если мы находимся в (m+1)-ой колонке, то вернемся в m-ую.

j += dir;

}

Выводим ответ – элемент из строки x и столбца y.

printf("%d\n",mas[x][y]);

Реализация алгоритма – двойной цикл

#include <stdio.h>

#define MAX 110

int i, j, n, m, x, y;

int temp, start, end, dir, cnt;

int mas[MAX][MAX];

int main(void)

{

scanf("%d %d %d %d",&n,&m,&x,&y);

dir = 1; cnt = 0;

start = 1; end = m;

for(i = 1; i <= n; i++)

{

for(j = start; j != end + dir; j += dir)

mas[i][j] = cnt++;

dir = -dir;

temp = start; start = end; end = temp; // swap(start,end);

}

printf("%d\n",mas[x][y]);

return 0;

}